package binarysearch;

/**
 * 74.搜索二维矩阵
 * 给你一个满足下述两条属性的 m x n 整数矩阵：
 * ● 每行中的整数从左到右按非严格递增顺序排列。
 * ● 每行的第一个整数大于前一行的最后一个整数。
 * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
 */
public class searchMatrix {

    /**
     * hot100一刷
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] nums = new int[matrix.length * matrix[0].length];
        int index = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                nums[index++] = matrix[i][j];
            }
        }
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }


    /**
     * hot100二刷
     */
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int top = 0, col = matrix[0].length - 1;
            while (top <= matrix.length - 1 && col >= 0) {
                if (matrix[top][col] == target) {
                    return true;
                } else if (matrix[top][col] > target) {
                    col--;
                } else {
                    top++;
                }
            }
            return false;
        }
    }



}
